package leetcode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 描述:
 *
 * @author Madison You
 * @created 11:30
 */
public class Mid_98_IsValidBST {
    public static void main(String[] args) {
        TreeNode treeNode = CreateTreeNode.arrayToTreeNode(new Integer[]{5,1,4,null,null,3,6});
        boolean validBST = new Mid_98_IsValidBST().isValidBST(treeNode);
        System.out.println(validBST);
    }

    public boolean isValidBST(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) return false;
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    /*判断左节点是否全部小于node值*/
                    if(!checkLeft(node.left, node.val)) return false;
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    /*判断右节点是否全部大于node值*/
                    if (!checkRight(node.right, node.val)) return false;
                    queue.offer(node.right);
                }
            }
        }
        return true;
    }

    private boolean checkRight(TreeNode root, int val) {
        if (root == null) return true;
        if (root.val <= val) return false;
        return checkRight(root.left, val) && checkRight(root.right, val);
    }

    private boolean checkLeft(TreeNode root, int val) {
        if (root == null) return true;
        if (root.val >= val) return false;
        return checkLeft(root.left, val) && checkLeft(root.right, val);
    }
}
